package twice.class02;

public class class01_MeregeSort {
    //递归形式归并排序
    public static void meregeSort(int[] arr){
        if(arr == null|| arr.length<2){
            return;
        }
        process(arr,0,arr.length-1);
    }
    static void process(int[] arr,int L,int R){
        if(L==R){
            return;
        }
        int mid = L + (R-L)/2;
        process(arr,L,mid);
        process(arr,mid+1,R);
        merge(arr,L,mid,R);
    }
    static void merge(int[] arr,int L,int mid,int R){
        int[] temp = new int[R - L + 1];
        int i = 0;
        int p1 = L;
        int p2 = mid + 1;
        while(p1 <= mid && p2 <= R){
            temp[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
        }
        while (p1 <= mid) {
            temp[i++] = arr[p1++];
        }
        while (p2 <= R) {
            temp[i++] = arr[p2++];
        }
        for(i = 0; i < temp.length;i++){
            arr[L++] = temp[i];
        }
    }
    //非递归写法
    public static void meregeSort1(int[] arr){
        if(arr == null|| arr.length<2){
            return;
        }
        int meregeSize = 1;
        int N = arr.length;
        while(meregeSize < N){
            int L = 0;
            while(L < N){
                int M = L + meregeSize - 1;
                if(M >= N){break;}
                int R = Math.min(M + meregeSize, N - 1);
                merge(arr,L,M,R);
                L = R + 1;
            }
            if(meregeSize > N / 2){break;}
            meregeSize <<= 1;
        }
    }

    public static void main(String[] args) {
        int[] arr = new int[]{8,7,5,2,6,4,3,1,9,3,9,3};
        meregeSort1(arr);
        for (int i : arr) {
            System.out.print(i);
        }
    }
}
